/**
 * Created by L.jp
 * Description:给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 * User: 86189
 * Date: 2022-08-26
 * Time: 23:09
 */
public class Solution {
    public static String LCS (String str1, String str2) {
        //还是以最长公共子串的长度为原型进行构造数组，我们可以通过公共子串的长度和每一次公共子串结束的位置来找到最长公共子串
        int n= str1.length();
        int m=str2.length();
        int max=0;
        int endPox=-1;
        int[][] dp=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //更新公共子串的长度
                if(str1.charAt(i-1)== str2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=0;
                }
                //更新最长公共子串的长度
                if(dp[i][j]>max) {
                    max = Math.max(max, dp[i][j]);
                    endPox = i - 1;
                }
            }
        }
        //endPox-max+1是最长公共子串开始的位置，endPox+1是最长公共子串结束的位置
        return str1.substring(endPox-max+1,endPox+1);
    }
    
    public static void main(String[] args) {
        String s1="abjhdjaads";
        String s2="abjhhsaadd";
        System.out.println(LCS(s1, s2));
    }
}
